//
// Created by WQM on 2020/10/12.
//
/**
 * 排序
 *
 *
 * 插入排序
 *      直接插入排序  StraightInsertSort(List R,int n)
 *      折半插入排序
 *      表插入排序
 *      希尔排序
 * 交换排序
 *      冒泡排序      BubbleSort()
 *      快速排序      QuickPartion(List R,int low,int high ),QuickSort(List R,int low ,int high)
 * 选择排序
 *      直接选择排序  SelectSort(List R,int n)
 *      堆排序       Sift(List R, int k, int m)，HeapSort(List R)
 * 归并排序
 *      有序序列的排序 Merge(List a,List R,int h,int m,int n)
 *      二路归并排序
 */

#ifndef TEST_SORT_H
#define TEST_SORT_H

#endif //TEST_SORT_H
typedef struct {
    int age;
} ItemType;
typedef struct {
    int key;
    ItemType otheritem;
} RecordType;
const int n = 10;                       //待排序的元素个数
typedef RecordType List[n + 1];

/**
 *
 * 对R进行直接插入排序
 * 稳定性：       稳定
 * 空间复杂度：    O(1)
 * 时间复杂度：    O(n^2)
 * */
void StraightInsertSort(List R, int n) {

    int i, j;
    for (i = 2; i < n; i++) {
        R[0] = R[i];
        j = i - 1;
        while (R[0].key < R[j].key) {    //与岗哨比较，直至健值不大于岗哨健值
            R[j + 1] = R[j];             // 将第j个记录赋值给第j+1个记录
            j--;
        }
        R[j + 1] = R[0];
    }
}

/**
 * 冒泡排序
 * 稳定性：       稳定
 * 空间复杂度：
 * 时间复杂度：    O(n^2)
 *
 * */
void BubbleSort(List R, int n) {
    int i, j, endsort;
    RecordType temp;
    for (i = 1; i <= n - 1; i++) {
        endsort = 0;
        for (j = 1; j <= n - i - 1; j++) { //n-i-1 剩余未排序的列表
            if (R[j].key > R[j + 1].key) { //如果出现逆序 则交换记录
                temp = R[j];
                R[j] = R[j + 1];
                R[j + 1] = temp;
                endsort = 1;
            }
        }
        if (endsort == 0)break;
    }
}

/**
 * 一趟快速排序
 * QuickPartion(List R,int low,int high )
 * 稳定性：       不稳定
 * 空间复杂度：
 * 时间复杂度：    O(n^2)
 * */
int QuickPartion(List R, int low, int high) {
    //对R[low],R[low+1],...,R[high] 子序列进行一趟快速排序
    RecordType x;
    x = R[low];                                         //赋初值
    while (low < high) {
        while ((low < high) && (R[high].key >= x.key)) {
            high--;
        }
        R[low] = R[high];                               //自尾端进行比较，将比x健值小的记录移到低端
        while ((low < high) && (R[low].key <= x.key)) {
            low++;
        }
        R[high] = R[low];                               //自尾端进行比较，将比x健值大的移到高端
    }
    R[low] = x;                                         //一趟快速排序结束，将x移到其最终位置
    return low;
}

/**
 * 完整递归快速排序
 * 稳定性：       不稳定
 * 空间复杂度：
 * 时间复杂度：    O(n^2)   不适合已经有序 适合数量大且无序
 *
 * */
void QuickSort(List R, int low, int high) {
    int temp;
    if (low < high) {
        temp = QuickPartion(R, low, high);
        QuickSort(R, low, temp - 1);
        QuickSort(R, temp + 1, high);
    }
}

/**
 * 直接选择排序
 * 稳定性：       不稳定
 * 空间复杂度：
 * 时间复杂度：    O(n^2)  不适合n较大的情况
 * */

void SelectSort(List R, int n) {
    int min, j, i;
    RecordType temp;
    for (i = 1; i < n - 1; i++) {                   //每次循环选出最小值
        min = i;                                    //假设第i个值最小
        for (j = i + 1; j < n; j++) {
            if (R[j].key < R[min].key) min = j;
            if (min != i) {//swap(R[min],R[i]);     //将最小值和第i个记录交换
                temp = R[i];
                R[i] = R[min];
                R[min] = temp;
            }
        }
    }
}

/**
 * 筛选：自堆顶向下调整的过程 Sift
 * */
void Sift(List R, int k, int m) {
    /*假设R[k],R[k+1],...,R[m]是以R[k]为根的完全二叉树R[k]的左右子树均满足堆的性质
     * 本算法调整R[k]使整个序列R【k】满足堆顶性质
     * */
    int i, j, x;
    RecordType t;
    i = k;                                            //根
    j = i * 2;                                        //左孩子
    x = R[k].key;
    t = R[k];
    while (j < m) {
        if ((j < m) && (R[j].key > R[j + 1].key)) j++;//若存在右子树，且右子树的根的关键字小，则沿右分支筛选
        if (x < R[j].key)break;                       //筛选完毕
        else {
            R[i] = R[j];
            i = j;
            j = 2 * i;
        }
        R[i] = t;                                      //填入恰当位置
    }
}

/**
 * 堆排序
 * 稳定性：       不稳定
 * 空间复杂度：      O(1)一个临时交换空间
 * 时间复杂度：    O(nlog2n)
 *
 * */
void HeapSort(List R) {
    //对R进行排序，排序完成后R按自小到大排序
    int i;
    RecordType temp;
    for (i = n / 2; i >= 1; i++) {
        Sift(R, i, n);                                   //从第n/2个记录开始筛选建堆
    }
    for (i = n; i >= 2; i--) {
        temp = R[1];                                     //
        R[1] = R[i];                                     //将堆顶元素和堆中最后一个元素交换
        R[i] = temp;                                     //
        Sift(R, 1, i - 1);                         //调整R[1]使R[1],,,,R[i-1]变成堆
    }
}

/**
 * 有序序列的排序
 * 稳定性：       稳定
 * 空间复杂度：
 * 时间复杂度：    O(n-h+1)
 * */
/**
 * 有序排序
 * */
void Merge(List a, List R, int h, int m, int n) {
    //将ah，，，，am 和am+1，。。。an 两个有序序列合并成一个有序序列 Rh,,,,Rn
    int k = h;
    int j = m + 1;
    while ((h <= m) && (j <= n)) {
        if (a[h].key <= a[j].key) {           //a[h]健值小，送入R【h】并修改h值
            R[k] = a[h];
            h++;
        } else {                              //a[j]健值小，送入R【k】并修改j值
            R[k] = a[j];
            j++;
        }
        k++;
    }
    while (h <= m) {                           //j>n,将ah，。。。am剩余部分插入R的尾部
        R[k] = a[h];
        h++;
        k++;
    }
    while (n <= n) {                           //h>m,将 am+1，。。。。an剩余部分插入R的尾部
        R[k] = a[j];
        j++;
        k++;
    }
}

/**
 * 一次二路归并
 * */
void MergePass(List a, List b, int n, int h) {
    int i = 1;
    while (i <= n - 2 * h + 1) {
        Merge(a, b, i, i + h - 1, i + 2 * h - 1);
        i += 2 * h;
    }
    if (i + h - 1 < n) {
        Merge(a, b, i, i + h - 1, n);
    } else {
        for (int t = i; t <= n; t++) {
            b[t] = a[t];
        }
    }

}

/**
 * 完整二路归并
 * 稳定性：       稳定
 * 空间复杂度：
 * 时间复杂度：    O(nlog2n)
 * */
void MergeSort(List a, int n) {
    List b;
    int m = 1;
    while (m < n) {
        MergePass(a, b, n, m);                  //将序列a中有序子序列合并到b
        m = 2 * m;                              //将子序列的长度扩大一倍
        MergePass(b, a, n, m);                  //将序列b中有序子序列合并到a
        m = 2 * m;                              //将子序列的长度扩大一倍
    }
}